#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <limits>
#include <cmath>

namespace {

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val):val(val),left(NULL),right(NULL){}
};

void MakeTree(TreeNode* &root, int depth, int &data) {
    if (depth > 0) {
        root = new TreeNode(data);
        root->val = ++data;
        MakeTree(root->left, depth - 1, data);
        MakeTree(root->right, depth - 1, data);
    }
    else {
        root = NULL;
    }
}

TreeNode* MiddleNode(const int start, const int end) {
    if (start > end) return NULL;
    int num = start + (end - start) / 2;
    TreeNode *root = new TreeNode(num);
    root->left = MiddleNode(start, num - 1);
    root->right = MiddleNode(num + 1, end);
    return root;
}

void MakeTree2(TreeNode* &root, int depth, int &data) {
    if (depth > 0) {
        int num = pow(2, depth) - 2;
        root = MiddleNode(data, data + num);
    }
    else {
        root = NULL;
    }
}

// 层序遍历打印
void PrintTree(const std::string& prefix, const TreeNode *root, int dir = 0) {
    if (root) {
        std::cout << prefix;
        std::string newPrefix = prefix;
        if (dir == 1) {
            std::cout << "├──";
            newPrefix += "│  ";
        }
        else if (dir == 2) {
            std::cout << "└──";
            newPrefix += "   ";
        }
        std::cout << root->val << std::endl;

        PrintTree(newPrefix, root->right, 1);
        PrintTree(newPrefix, root->left, 2);
    }
}

void PrintTree(const TreeNode *root) {
    std::cout << std::endl;
    PrintTree("", root);
}

void PreOrder(TreeNode *root) {
    if (root) {
        std::cout << root->val;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void InOrder(TreeNode *root) {
    if (root) {
        InOrder(root->left);
        std::cout << root->val;
        InOrder(root->right);
    }
}

void PostOrder(TreeNode *root) {
    if (root) {
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout << root->val;
    }
}

// 层序遍历
void LevelOrderSub(TreeNode *root) {
    if (root) {
        if (root->left)
            std::cout << root->left->val;
        if (root->right)
            std::cout << root->right->val;
        LevelOrderSub(root->left);
        LevelOrderSub(root->right);
    }
}

void LevelOrder(TreeNode *root) {
    if (root) {
        std::cout << root->val;
        LevelOrderSub(root);
    }
}

// 翻转二叉树
TreeNode* InvertTree(TreeNode *root) {
    if (!root) return NULL;

    TreeNode *right = InvertTree(root->right);
    TreeNode *left = InvertTree(root->left);

    root->left = right;
    root->right = left;
    return root;
}

// 翻转二叉树非递归实现
TreeNode* InvertTree2(TreeNode *root) {
    if (!root) return NULL;

    std::queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        TreeNode *head = que.front();
        TreeNode *temp = head->left;
        head->left = head->right;
        head->right = temp;
        que.pop();
        if (!temp->left) que.push(temp->left);
        if (!temp->right) que.push(temp->right);
    }
    return root;
}

int MaxDepth(TreeNode *root) {
    if (!root) return 0;
    int left = MaxDepth(root->left) + 1;
    int right = MaxDepth(root->right) + 1;
    return left > right ? left : right;
}

// 是否二叉搜索树
bool IsValidBST(TreeNode *root) {
    if (!root) return false;
    std::stack<TreeNode*> st;
    double inorder = -std::numeric_limits<double>::max();
    while (!st.empty() || root) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        if (root->val <= inorder) return false;
        inorder = root->val;
        root = root->right;
    }
    return true;
}

// 是否有路径和等于sum
bool HasPathSum(TreeNode *root, int sum) {
    if (!root) return false;

    sum -= root->val;
    if (!root->left && !root->right) return sum == 0;
    return HasPathSum(root->left, sum) || HasPathSum(root->right, sum);
}

bool HasPathSum2(TreeNode *root, int sum) {
    if (!root) return false;

    // 自己能不能形成一条路径
    if (root->val == sum) return true;

    sum -= root->val;
    // 左右子节点能不能形成一条路径
    return HasPathSum2(root->right, sum) || HasPathSum2(root->left, sum);
}

// 节点数 O(n) 复杂度
int CountNodes(TreeNode *root) {
    if (!root) return 0;
    return 1 + CountNodes(root->right) + CountNodes(root->left);
}

// 完全二叉树节点数 O(logn*logn) 复杂度
// 中文语义
// 完全二叉树对应：Complete Binary Tree (完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐)
// 完美二叉树对应：Perfect Binary Tree (一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树)  (注： 国内的数据结构教材大多翻译为"满二叉树")
// 完满二叉树对应：Full Binary Tree (所有非叶子结点的度都是2) (只要你有孩子，你就必然是有两个孩子)
int CountNodes2(TreeNode *root) {
    if (!root) return 0;

    TreeNode *left = root, *right = root;
    int lh = 0, rh = 0;
    while (left) {
        left = left->left;
        lh++;
    }

    while (right) {
        right = right->right;
        rh++;
    }

    if (lh == rh) {
        return (int)pow(2, lh) - 1;
    }

    return 1 + CountNodes(root->right) + CountNodes(root->left);
}

void Handle() {
    TreeNode *root = NULL;
    int data = 0;
    MakeTree2(root, 3, data);
    PrintTree(root);

    std::cout << std::endl << "preorder: ";
    PreOrder(root);
    std::cout << std::endl << "inorder: ";
    InOrder(root);
    std::cout << std::endl << "postorder: ";
    PostOrder(root);
    std::cout << std::endl << "levelorder: ";
    LevelOrder(root);
    std::cout << std::endl;

    // TreeNode *invert = InvertTree(root);
    // std::cout << std::endl << "inverttree: ";
    // PrintTree(invert);
    // TreeNode *invert = InvertTree2(root);
    // std::cout << std::endl << "inverttree2: ";
    // PrintTree(invert);

    int depth = MaxDepth(root);
    std::cout << "max depth " << depth << std::endl;
    std::cout << "is valid BST " << IsValidBST(root) << std::endl;

    std::cout << "has path sum " << HasPathSum(root, 6) << std::endl;
    std::cout << "has path sum " << HasPathSum2(root, 6) << std::endl;

    std::cout << "tree node num " << CountNodes(root) << std::endl;
    std::cout << "tree node num2 " << CountNodes2(root) << std::endl;
}

}

void HandleTree() {
    Handle();
}
